﻿#ifndef __SBCTN_H__
#define __SBCTN_H__

#if _MSC_VER
#pragma once
#pragma warning(push)
#pragma warning(disable:4127)
#pragma warning(disable:4200)
#endif

#if __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Warray-bounds"
#endif

#include "sbcs.h"
#include "sbtpl.h"

K_EXTERN_C_BEGIN

//////////////////////////////////////////////////////////////////////////
// array
typedef struct kArr
{
	kbyte*				data;
	kssize_t			count;
	kssize_t			capa;
} kArr;

#define K_ARR_DECL(name,type)\
	typedef struct name name;\
	typedef type name##Type;\
	struct name { type* data; kssize_t count; kssize_t capa; };

#define k_arr_nth(p,n)						(((p)->data)[(kssize_t)(n)])
#define k_arr_inv(p,n)						(((p)->data)[((p)->count-1-(kssize_t)(n))])
#define k_arr_count(p)						((p)->count)
#define k_arr_capacity(p)					((p)->capa)
#define k_arr_data(p)						((p)->data)
#define k_arr_sizeof(name)					(sizeof(name##Type))
#define k_arr_is_empty(p)					((p)->count==0)
#define k_arr_is_have(p)					((p)->count!=0)

#define k_arr_init(name,p,initcapa)\
	K_STMT_BEGIN{\
		(p)->data=NULL;\
		(p)->count=0;\
		(p)->capa=0;\
		if ((initcapa)>0)\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (initcapa));\
	}K_STMT_END

#define k_arr_disp(name,p)\
	K_STMT_BEGIN{ k_free((p)->data); }K_STMT_END

#define k_arr_set_capacity(name,p,newcapa)\
	K_STMT_BEGIN{ k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), newcapa); }K_STMT_END

#define k_arr_set_count(name,p,newcnt)\
	K_STMT_BEGIN{ k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name),(newcnt)); (p)->count=(newcnt); }K_STMT_END

#define k_arr_copy(name,p,o)\
	K_STMT_BEGIN{\
		if (!(o) || !(o)->count)\
			(p)->count=0;\
		else\
		{\
			kssize_t __n=(o)->count;\
			k_arr_set_count(name,p,__n);\
			memcpy((p)->data, (o)->data, __n*k_arr_sizeof(name));\
		}\
	}K_STMT_END

#define k_arr_blob(name,p,items,cnt)\
	K_STMT_BEGIN{\
		if ((kssize_t)(cnt)>0)\
		{\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->count+(kssize_t)(cnt));\
			memcpy(&k_arr_nth(p, (p)->count), (items), k_arr_sizeof(name)*(kssize_t)(cnt));\
			(p)->count+=(kssize_t)(cnt);\
		}\
	}K_STMT_END

#define k_arr_remove_nth(name,p,n)\
	K_STMT_BEGIN{\
		k_assert((kssize_t)(n)<(p)->count, "remove index overflow!");\
		{\
			name##Type* __t=&k_arr_nth(p,n);\
			if ((kssize_t)(n)!=(p)->count-1)\
				memmove(__t, __t+1, k_arr_sizeof(name)*((p)->count-((kssize_t)(n)+1)));\
			(p)->count--;\
		}\
	}K_STMT_END

#define k_arr_remove_range(name,p,idx,cnt)\
	K_STMT_BEGIN{\
		kssize_t __s=(kssize_t)(idx)+(kssize_t)(cnt);\
		kssize_t __cnt=(p)->count;\
		if ((kssize_t)(idx)<__cnt && __s<__cnt)\
		{\
			if (__s!=__cnt-1)\
				memmove(&k_arr_nth(p,idx), &k_arr_nth(p,__s), (__cnt-__s)*k_arr_sizeof(name));\
			(p)->count-=(kssize_t)cnt;\
		}\
	}K_STMT_END

#define k_arr_clear(name,p)\
	((p)->count=0)

#define k_arr_find(name,p,start,func_ud_ptr,userdata,ret)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (*(ret)=-1, __i=(kssize_t)(start); __i<__cnt; __i++)\
		{\
			if (func_ud_ptr(userdata, &k_arr_nth(p,__i)))\
			{\
				*(ret)=__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_arr_sort(name,p,func)\
	(k_qsort((p)->data, (p)->count, k_arr_sizeof(name), func))

#define k_arr_sort_context(name,p,func,userdata)\
	(k_qsort_context((p)->data, (p)->count, k_arr_sizeof(name), func, userdata))

/* value type */
#define k_arr_add(name,p,item)\
	K_STMT_BEGIN{\
		if ((p)->count>=(p)->capa)\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->capa+1);\
		k_arr_nth(p,(p)->count)=(item);\
		(p)->count++;\
	}K_STMT_END

#define k_arr_reserve(name,p)\
	K_STMT_BEGIN{\
		if ((p)->count>=(p)->capa)\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->capa+1);\
		(p)->count++;\
	}K_STMT_END

#define k_arr_insert(name,p,idx,item)\
	K_STMT_BEGIN{\
		if ((kssize_t)(idx)<=(p)->count)\
		{\
			if ((p)->count>=(p)->capa)\
				k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->capa+1);\
			memmove((p)->data+(kssize_t)(idx)+1, (p)->data+(kssize_t)(idx), ((p)->count-(kssize_t)(idx))*k_arr_sizeof(name));\
			k_arr_nth(p,idx)=(item);\
			(p)->count++;\
		}\
	}K_STMT_END

#define k_arr_remove(name,p,item)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
		{\
			if (k_arr_nth(p,__i)==(item))\
			{\
				name##Type* __t=&k_arr_nth(p,__i);\
				memmove(__t, __t+1, k_arr_sizeof(name)*(__cnt-(__i+1)));\
				__cnt--;\
				break;\
			}\
		}\
		(p)->count=__cnt;\
	}K_STMT_END

#define k_arr_remove_cmp(name,p,func_ptr_item,item)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
		{\
			name##Type* __t=&k_arr_nth(p,__i);\
			if (func_ptr_item(__t,(item)))\
			{\
				memmove(__t, __t+1, k_arr_sizeof(name)*(__cnt-(__i+1)));\
				__cnt--;\
				break;\
			}\
		}\
		(p)->count=__cnt;\
	}K_STMT_END

#define k_arr_contains(name,p,item,retintptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (*(retintptr)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (k_arr_nth(p,__i)==(item))\
			{\
				*(retintptr)=(int)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_arr_contains_cmp(name,p,func_ptr_item,item,retintptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (*(retintptr)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (func_ptr_item(&k_arr_nth(p,__i),(item)))\
			{\
				*(retintptr)=(int)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_arr_foreach(name,p,func_ud_ptr,userdata)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func_ud_ptr(userdata, &k_arr_nth(p,__i));\
	}K_STMT_END

#define k_arr_loopeach(name,p,func_ptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func_ptr(&k_arr_nth(p,__i));\
	}K_STMT_END

K_INLINE void k_arr_inl_expand(kpointer arr, kssize_t size, kssize_t cnt)
{
	kArr* p=(kArr*)arr;
	if (p->count<cnt)
	{
		p->capa=p->capa+p->capa/2;
		if (p->capa<cnt)
			p->capa=cnt;
		p->data=k_renew(p->data, p->capa*size, kbyte);
	}
}


//////////////////////////////////////////////////////////////////////////
// pointer array
K_ARR_DECL(kPtrArr, kpointer);

#define k_parr_nth(p,i)				k_arr_nth(p,i)
#define k_parr_count(p)				k_arr_count(p)
#define k_parr_capacity(p)			k_arr_capacity(p)
#define k_parr_is_empty(p)			k_arr_is_empty(p)
#define k_parr_is_have(p)			k_arr_is_have(p)

#define k_parr_init(p, capacity)\
	k_arr_init(kPtrArr, p, capacity)

#define k_parr_disp(p)\
	k_arr_disp(kPtrArr, p)

#define k_parr_clear(p)\
	k_arr_clear(kPtrArr, p)

#define k_parr_set_capacity(p,capa)\
	k_arr_set_capacity(kPtrArr, p, capa)

#define k_parr_set_count(p,count)\
	k_arr_set_count(kPtrArr, p, count)

#define k_parr_remove_nth(p, index)\
	k_arr_remove_nth(kPtrArr, p, index)

#define k_parr_remove_range(p, index, count)\
	k_arr_remove_range(kPtrArr, p, index, count)

#define k_parr_remove(p, item)\
	k_arr_remove(kPtrArr, p, item)

#define k_parr_add(p, item)\
	k_arr_add(kPtrArr, p, item)

#define k_parr_reserve(p)\
	k_arr_reserve(kPtrArr, p)

#define k_parr_insert(p, index, item)\
	k_arr_insert(kPtrArr, index, item)

#define k_parr_sort(p, func)\
	k_arr_sort(kPtrArr, p, func)

#define k_parr_sort_context(p, func, userdata)\
	k_arr_sort_context(kPtrArr, p, func, userdata)

#define k_parr_find(p, start, pred_ud_ptr, userdata, ret)\
	k_arr_find(kPtrArr, p, start, pred_ud_ptr, userdata, ret)

#define k_parr_contains(p, data, ret)\
	k_arr_contains(kPtrArr, p, data, ret)

#define k_parr_swap_data(p, newdata, newcount, olddataptr)\
	K_STMT_BEGIN{\
		kpointer __save=((kPtrArr*)(p))->data;\
		((kPtrArr*)(p))->data=data;\
		((kPtrArr*)(p))->count=newcount;\
		((kPtrArr*)(p))->capa=newcount;\
		if (*(olddataptr)) *(olddataptr)=__save;\
	}K_STMT_END

#define k_parr_copy(p, o)\
	k_arr_copy(kPtrArr, p, o)

#define k_parr_foreach(p,func_ud_ptr,userdata)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=((kPtrArr*)(p))->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, k_arr_nth(p,__i));\
	}K_STMT_END

#define k_parr_loopeach(p,func_ptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=((kPtrArr*)(p))->count;\
		for (__i=0; __i<__cnt; __i++)\
			func_ptr(k_arr_nth(p,__i));\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// container
typedef struct kCtnr
{
	kbyte*				data;
	ksize_t				count;
} kCtnr;

#define K_CTNR_DECL(name,type)\
	typedef type name##Type;\
	typedef struct name { type* data; ksize_t count; } name

#if _SB_DEBUG_
#define k_ctnr_at_safe(p,n)				(((p)->data)[((ksize_t)(n)<(p)->count) ? (ksize_t)(n) : k_mesg_assert(#n, "overflow", __FILE__, __LINE__)])
#else
#define k_ctnr_at_safe(p,n)				(((p)->data)[(ksize_t)(n)])
#endif
#define k_ctnr_nth(p,n)					(((p)->data)[(ksize_t)(n)])
#define k_ctnr_count(p)					((p)->count)
#define k_ctnr_data(p)					((p)->data)
#define k_ctnr_size(name)				(sizeof(name##Type))
#define k_ctnr_set(p,n,i)				(((p)->data)[(ksize_t)(n)]=(i))
#define k_ctnr_is_empty(p)				((p)->count==0)
#define k_ctnr_is_have(p)				((p)->count!=0)

#define k_ctnr_init(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((ksize_t)(cnt)>0)\
		{\
			(p)->data=k_new((ksize_t)(cnt), name##Type);\
			(p)->count=(ksize_t)(cnt);\
		}\
		else\
		{\
			(p)->data=NULL;\
			(p)->count=0;\
		}\
	}K_STMT_END

#define k_ctnr_init_zero(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((ksize_t)(cnt)>0)\
		{\
			(p)->data=k_new_zero((ksize_t)(cnt), name##Type);\
			(p)->count=(ksize_t)(cnt);\
		}\
		else\
		{\
			(p)->data=NULL;\
			(p)->count=0;\
		}\
	}K_STMT_END

#define k_ctnr_disp(name, p)\
	k_delete((kpointer)(p)->data)

#define k_ctnr_reset(name, p)\
	K_STMT_BEGIN{ (p)->count=0; }K_STMT_END

#define k_ctnr_resize(name, p, cnt)\
	k_ctnr_set_count(name, p, cnt)

#define k_ctnr_expand(name, p, cnt)\
	k_ctnr_set_count(name, p, cnt)

#define k_ctnr_set_count(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((p)->count!=(ksize_t)(cnt))\
		{\
			(p)->data=k_renew((p)->data, (ksize_t)(cnt), name##Type);\
			(p)->count=(ksize_t)(cnt);\
		}\
	}K_STMT_END

#define k_ctnr_add_count(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((ksize_t)(cnt)!=0)\
		{\
			(p)->data=k_renew((p)->data, (p)->count+(ksize_t)(cnt), name##Type);\
			(p)->count+=(ksize_t)(cnt);\
		}\
	}K_STMT_END

#define k_ctnr_add(name,p,v)\
	K_STMT_BEGIN{\
		k_ctnr_add_count(name,p,1);\
		k_ctnr_nth(p,(p)->count-1)=(v);\
	}K_STMT_END

#define k_ctnr_zero(name, p)\
	memset((p)->data, 0, (p)->count*sizeof(name##Type))

#define k_ctnr_contains(name,p,item,ret)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(ret)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (k_ctnr_nth(p,__i)==item)\
			{\
				*(ret)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_ctnr_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, k_ctnr_nth(p, __i));\
	}K_STMT_END

#define k_ctnr_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(k_ctnr_nth(p, __i));\
	}K_STMT_END

#define k_ctnr_ptr_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, &k_ctnr_nth(p, __i));\
	}K_STMT_END

#define k_ctnr_ptr_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(&k_ctnr_nth(p, __i));\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// pointer container 
K_CTNR_DECL(kPtrCtnr, kpointer);

#define k_pctnr_at_safe(p,n)			k_ctnr_at_safe(p,n)
#define k_pctnr_nth(p,n)				k_ctnr_nth(p,n)
#define k_pctnr_count(p,n)				k_ctnr_count(p,n)
#define k_pctnr_data(p)					k_ctnr_data(p)

#define k_pctnr_init(p, count)\
	k_ctnr_init(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_initZero(p, count)\
	k_ctnr_initZero(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_disp(p)\
	k_ctnr_disp(kPtrCtnr, (kPtrCtnr*)p)

#define k_pctnr_set_count(p, count)\
	k_ctnr_set_count(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_add_count(p, count)\
	k_ctnr_add_count(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_add(p, item)\
	k_ctnr_add(kPtrCtnr, (kPtrCtnr*)p, (kpointer)item)

#define k_pctnr_zero(p)\
	k_ctnr_zero(kPtrCtnr, (kPtrCtnr*)p)

#define k_pctnr_foreach(p, func, userdata)\
	k_ctnr_foreach(kPtrCtnr, (kPtrCtnr*)p, func, userdata)

#define k_pctnr_loopeach(p, func)\
	k_ctnr_loopeach(kPtrCtnr, (kPtrCtnr*)p, func)


//////////////////////////////////////////////////////////////////////////
// common array & container
K_ARR_DECL(kByteArr, kbyte);
K_ARR_DECL(kIntArr, kint);
K_ARR_DECL(kUintArr, kuint);
K_ARR_DECL(kPcharArr, char*)						// kPtrArr
K_ARR_DECL(kPccharArr, const char*);				// kPtrArr
K_ARR_DECL(kAnyCbArr, kanycb);

K_CTNR_DECL(kByteCtn, kbyte);
K_CTNR_DECL(kIntCtn, kint);
K_CTNR_DECL(kUintCtn, kuint);
K_CTNR_DECL(kPcharCtn, char*);						// kPtrCtnr
K_CTNR_DECL(kPccharCtn, const char*);				// kPtrCtnr
K_CTNR_DECL(kAnyCbCtn, kanycb);


//////////////////////////////////////////////////////////////////////////
// list
typedef struct kListNode
{
	struct kListNode*	next;
	struct kListNode*	prev;
	kbyte				data[];
} kListNode;

typedef struct kList
{
	kListNode*			frst;
	kListNode*			last;
	kssize_t			count;
} kList;

#define K_LIST_DECL(name,type)\
	typedef struct name name;\
	typedef type name##Type;\
	struct name##Node { struct name##Node *next, *prev; type data; };\
	struct name { struct name##Node *frst, *last; kssize_t count; }

#define k_list_count(p)						((p)->count)
#define k_list_node_first(p)				((p)->last)
#define k_list_node_last(p)					((p)->frst)
#define k_list_data_first(p)				((p)->last->data)
#define k_list_data_last(p)					((p)->frst->data)
#define k_list_is_have(p)					((p)->count!=0)
#define k_list_is_empty(p)					((p)->count==0)

#define k_list_init(name,p)\
	K_STMT_BEGIN{\
		(p)->frst=NULL;\
		(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_list_disp(name,p)\
	K_STMT_BEGIN{\
		struct name##Node *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_clear(name,p)\
	K_STMT_BEGIN{\
		k_list_disp(name,p);\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_list_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node* __node=(node);\
		if (__node)\
		{\
			if (__node->next)\
				__node->next->prev=__node->prev;\
			else\
			{\
				k_assert_eq((p)->last, __node);\
				(p)->last=__node->prev;\
			}\
			if (__node->prev)\
				__node->prev->next=__node->next;\
			else\
			{\
				k_assert_eq((p)->frst, __node);\
				(p)->frst=__node->next;\
			}\
			(p)->count--;\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_remove_first(name,p)\
	k_list_remove_node(name, p, (p)->last)

#define k_list_remove_last(name,p)\
	k_list_remove_node(name, p, (p)->frst)

// value type
#define k_list_disp_cb(name,p,func_user_data,userdata)\
	K_STMT_BEGIN{\
		struct name##Node *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			func_user_data(userdata,__node->data);\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_append(name,p,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		__node->data=item;\
		if ((p)->frst)\
			(p)->frst->prev=__node;\
		else\
			(p)->last=__node;\
		__node->next=(p)->frst;\
		__node->prev=NULL;\
		(p)->frst=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_prepend(name,p,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		__node->data=item;\
		if ((p)->last)\
			(p)->last->next=__node;\
		else\
			(p)->frst=__node;\
		__node->prev=(p)->last;\
		__node->next=NULL;\
		(p)->last=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_remove(name,p,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
		{\
			if (__node->data==(item))\
			{\
				k_list_remove_node(name, p, __node);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_remove_cmp(name,p,func_data_item,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
		{\
			if (func_data_pitem(__node->data, item))\
			{\
				k_list_remove_node(name, p, __node);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_contains(name,p,item,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (__node->data==(item))\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_find(name,p,predicate_user_data,userdata,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (predicate_user_data(userdata, __node->data))\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_foreach(name,p,func_user_data,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_user_data(userdata, __node->data);\
	}K_STMT_END

#define k_list_loopeach(name,p,func_data)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_data(__node->data);\
	}K_STMT_END

// reference type
#define k_list_ref_disp_cb(name,p,func_user_pdata,userdata)\
	K_STMT_BEGIN{\
		struct name##Node *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			func_user_pdata(userdata,&__node->data);\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_ref_append(name,p,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		memcpy(&__node->data, pitem, sizeof(name##Type));\
		if ((p)->frst)\
			(p)->frst->prev=__node;\
		else\
			(p)->last=__node;\
		__node->next=(p)->frst;\
		__node->prev=NULL;\
		(p)->frst=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_ref_prepend(name,p,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		memcpy(&__node->data, pitem, sizeof(name##Type));\
		if ((p)->last)\
			(p)->last->next=__node;\
		else\
			(p)->frst=__node;\
		__node->prev=(p)->last;\
		__node->next=NULL;\
		(p)->last=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_ref_remove(name,p,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
		{\
			if (memcmp(&__node->data, pitem)==0)\
			{\
				k_list_remove_node(name, p, __node);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_remove_cmp(name,p,func_pdata_pitem,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __rcnode;\
		for (__rcnode=(p)->frst; __rcnode; __rcnode=__rcnode->next)\
		{\
			if (func_pdata_pitem(&__rcnode->data, pitem))\
			{\
				k_list_remove_node(name, p, __rcnode);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_contains(name,p,pitem,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (memcmp(&__node->data, pitem)==0)\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_find(name,p,predicate_user_pdata,userdata,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (predicate_user_pdata(userdata, &__node->data))\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_foreach(name,p,func_user_pdata,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_user_pdata(userdata, &__node->data);\
	}K_STMT_END

#define k_list_ref_loopeach(name,p,func_pdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_pdata(&__node->data);\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// node list
typedef struct kNlNode
{
	struct kNlNode*		next;
	struct kNlNode*		prev;
} kNlNode;

typedef struct kNodeList
{
	kNlNode*			frst;
	kNlNode*			last;
	ksize_t				count;
} kNodeList;

#define K_NODELIST_DECL(name,type)\
	typedef struct name name;\
	typedef type name##Type;\
	struct name { type* frst; type* last; ksize_t count; }

#define k_nodelist_count(p)				((p)->count)
#define k_nodelist_first(p)				((p)->last)
#define k_nodelist_last(p)				((p)->frst)
#define k_nodelist_is_have(p)			((p)->count!=0)
#define k_nodelist_is_empty(p)			((p)->count==0)

#define k_nodelist_init(name,p)\
	K_STMT_BEGIN{\
		(p)->frst=NULL;\
		(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_nodelist_disp(name,p)\
	K_STMT_BEGIN{\
		name##Type *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_nodelist_disp_cb(name,p,func1)\
	K_STMT_BEGIN{\
		name##Type *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			func1(__node);\
		}\
	}K_STMT_END

#define k_nodelist_append(name,p,item)\
	K_STMT_BEGIN{\
		if ((p)->frst)\
			(p)->frst->prev=(item);\
		else\
			(p)->last=(item);\
		(item)->next=(p)->frst;\
		(item)->prev=NULL;\
		(p)->frst=(item);\
		(p)->count++;\
	}K_STMT_END

#define k_nodelist_prepend(name,p,item)\
	K_STMT_BEGIN{\
		if ((p)->last)\
			(p)->last->next=(item);\
		else\
			(p)->frst=(item);\
		(item)->prev=(p)->last;\
		(item)->next=NULL;\
		(p)->last=(item);\
		(p)->count++;\
	}K_STMT_END

#define k_nodelist_clear(name,p)\
	K_STMT_BEGIN{\
		k_nodelist_disp(name,p);\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_nodelist_clear_cb(name,p,func_1)\
	K_STMT_BEGIN{\
		k_nodelist_disp_cb(name,p,func_1);\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_nodelist_remove(name,p,item,func_1)\
	K_STMT_BEGIN{\
		if (item!=NULL)\
		{\
			name##Type* __node=(name##Type*)(item);\
			if (__node->next)\
				__node->next->prev=__node->prev;\
			else\
			{\
				k_assert_eq((p)->last, __node);\
				(p)->last=__node->prev;\
			}\
			if (__node->prev)\
				__node->prev->next=__node->next;\
			else\
			{\
				k_assert_eq((p)->frst, __node);\
				(p)->frst=__node->next;\
			}\
			(p)->count--;\
			func_1(__node);\
		}\
	}K_STMT_END

#define k_nodelist_remove_first(name,p,func_1)\
	k_nodelist_remove(name, (p)->last,func_1)

#define k_nodelist_remove_last(name,p,func_1)\
	k_nodelist_remove(name, (p)->frst,func_1)

#define k_nodelist_unlink(name,p,item)\
	K_STMT_BEGIN{\
		if (item!=NULL)\
		{\
			name##Type* __node=(name##Type*)(item);\
			if (__node->next)\
				__node->next->prev=__node->prev;\
			else\
			{\
				k_assert_eq((p)->last, __node);\
				(p)->last=__node->prev;\
			}\
			if (__node->prev)\
				__node->prev->next=__node->next;\
			else\
			{\
				k_assert_eq((p)->frst, __node);\
				(p)->frst=__node->next;\
			}\
			(p)->count--;\
			__node->prev=__node->next=NULL;\
		}\
	}K_STMT_END

#define k_nodelist_contains(name,p,item,retcham)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (*(retcham)=FALSE, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (__node==(item))\
			{\
				*(retcham)=TRUE;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_nodelist_find(name,p,predicate_user_node,userdata,retcham)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (*(retcham)=FALSE, __node=(p)->last; __node; __node=__node->prev)\
		{\
			if (predicate_user_node(userdata,__node))\
			{\
				*(retcham)=TRUE;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_nodelist_foreach(name,p,func_user_node,userdata)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_user_node(userdata,__node);\
	}K_STMT_END

#define k_nodelist_loopeach(name,p,func_node)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_node(__node);\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// pointer list
K_LIST_DECL(kPtrList, kpointer);

#define k_plist_count(p)				k_list_count(p)
#define k_plist_first(p)				k_list_data_first(p)
#define k_plist_last(p)					k_list_data_last(p)
#define k_plist_peek_first(p)			k_list_node_first(p)
#define k_plist_peek_last(p)			k_list_node_last(p)
#define k_plist_is_have(p)				k_list_is_have(p)
#define k_plist_is_empty(p)				k_list_is_empty(p)

#define k_plist_init(p)\
	k_list_init(kPtrList, p)

#define k_plist_disp(p)\
	k_list_disp(kPtrList, p)

#define k_plist_disp_cb(p,func_user_data,userdata)\
	k_list_disp_cb(kPtrList, p, func_user_data, userdata)

#define k_plist_append(p,item)\
	k_list_append(kPtrList, p, item)

#define k_plist_prepend(p,item)\
	k_list_prepend(kPtrList, p, item)

#define k_plist_clear(p)\
	k_list_clear(kPtrList, p)

#define k_plist_remove(p,item)\
	k_list_remove(kPtrList, p, item)

#define k_plist_remove_first(p)\
	k_list_remove_first(kPtrList, p)

#define k_plist_remove_last(p)\
	k_list_remove_last(kPtrList, p)

K_INLINE kcham k_plist_contains(kPtrList* p, kpointer item)
{
	struct kPtrListNode* node;
	k_list_contains(kPtrList, p, item, &node);
	return node!=NULL;
}

K_INLINE kcham k_plist_find(kPtrList* p, kcham (*pred)(kpointer, kpointer), kpointer userdata)
{
	struct kPtrListNode* node;
	k_list_find(kPtrList, p, pred, userdata, &node);
	return node!=NULL;
}

#define k_plist_foreach(p,func_user_data,userdata)\
	k_list_foreach(kPtrList, p, func_user_data, userdata)

#define k_plist_loopeach(p,func_data)\
	k_list_loopeach(kPtrList, p, func_data)


//////////////////////////////////////////////////////////////////////////
// solo list
typedef struct kSlist
{
	struct kSlist*		next;
	kbyte				data[];
} kSlist;

#define K_SLIST_DECL(name,type)\
	typedef type name##Type;\
	typedef struct name { struct name* next; type data; } name;

#define k_slist_last(p)\
	k_slist_inl_last(p)

#define k_slist_nth(p,nth)\
	k_slist_inl_nth(p, nth)

#define k_slist_data(p,nth)\
	(((kSlist*)k_slist_inl_nth(p, nth))->data)

#define k_slist_count(p)\
	k_slist_inl_count(p)

#define k_slist_delete(name, p, ptrptr)\
	K_STMT_BEGIN{\
		if ((p)==NULL)\
			*(ptrptr)=NULL;\
		else\
		{\
			name* __n=(p)->next;\
			k_delete(p);\
			*(ptrptr)=__n;\
		}\
	}K_STMT_END

#define k_slist_disp(name, p)\
	K_STMT_BEGIN{\
		name* __n;\
		name* __p;\
		for (__p=(p); __p; __p=__n)\
		{\
			__n=__p->next;\
			k_delete(__p);\
		}\
	}K_STMT_END

#define k_slist_disp_func(name, p, func_1)\
	K_STMT_BEGIN{\
		name* __n;\
		name* __p;\
		for (__p=(p); __p; __p=__n)\
		{\
			__n=__p->next;\
			func_1(__p);\
		}\
	}K_STMT_END

#define k_slist_concat(name, p1, p2, ptrptr)\
	K_STMT_BEGIN{\
		if ((p2)==NULL)\
			*(ptrptr)=(p1);\
		else\
		{\
			if ((p1)==NULL)\
				*(ptrptr)=(p2);\
			else\
			{\
				name* __l=(name*)k_slist_last(p1);\
				__l->next=(p2);\
				*(ptrptr)=(p1);\
			}\
		}\
	}K_STMT_END

#define k_slist_append(name, p, item, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_1(name);\
		__np->next=NULL;\
		__np->data=item;\
		if ((p)==NULL)\
			*(ptrptr)=__np;\
		else\
		{\
			name* __l=(name*)k_slist_last(p);\
			__l->next=__np;\
			*(ptrptr)=(p);\
		}\
	}K_STMT_END

#define k_slist_prepend(name, p, item, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_1(name);\
		__np->next=(p);\
		__np->data=item;\
		*(ptrptr)=__np;\
	}K_STMT_END

#define k_slist_reserve_append(name, p, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_0(name);\
		if ((p)==NULL)\
			*(ptrptr)=__np;\
		else\
		{\
			name* __l=(name*)k_slist_last(p);\
			__l->next=__np;\
			*(ptrptr)=(p);\
		}\
	}K_STMT_END

#define k_slist_reserve_prepend(name, p, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_0(name);\
		__np->next=(p);\
		*(ptrptr)=__np;\
	}K_STMT_END

#define k_slist_insert(name, p, sib, item, ptrptr)\
	K_STMT_BEGIN{\
		if ((p)==NULL)\
		{\
			name* __np=k_new_0(name);\
			__np->next=NULL;\
			__np->data=item;\
			*(ptrptr)=__np;\
		}\
		else\
		{\
			name* __l=NULL;\
			name* __np;\
			for (__np=(p); __np; __l=__np, __np=__l->next)\
			{\
				if (__np==(sib))\
					break;\
			}\
			__np=k_new_1(name);\
			__np->data=item;\
			if (__l==NULL)\
			{\
				__np->next=(p);\
				*(ptrptr)=__np;\
			}\
			else\
			{\
				__np->next=__l->next;\
				__l->next=__np;\
				*(ptrptr)=(p);\
			}\
		}\
	}K_STMT_END

#define k_slist_insert_nth(name, p, nth, item, ptrptr)\
	K_STMT_BEGIN{\
		kint __h=nth;\
		if (__h<0)\
		{\
			k_slist_append(name, p, item, ptrptr);\
		}\
		else if (__h==0)\
		{\
			k_slist_prepend(name, p, item, ptrptr);\
		}\
		else\
		{\
			name* __np=k_new_1(name);\
			__np->data=item;\
			if (p==NULL)\
			{\
				__np->next=NULL;\
				*(ptrptr)=__np;\
			}\
			else\
			{\
				name* __t=(p);\
				name* __v=NULL;\
				while (__h-->0 && __t)\
				{\
					__v=__t;\
					__t=__t->next;\
				}\
				if (__v)\
				{\
					__np->next=__v->next;\
					__v->next=__np;\
					*(ptrptr)=(p);\
				}\
				else\
				{\
					__np->next=(p);\
					*(ptrptr)=__np;\
				}\
			}\
		}\
	}K_STMT_END

#define k_slist_remove(name, p, item, ptrptr)\
	K_STMT_BEGIN{\
		name* __r=(p);\
		name* __t=(p);\
		name* __v=NULL;\
		while (__t)\
		{\
			if (__t->data==item)\
			{\
				if (__v)\
					__v->next=__t->next;\
				else\
					__r=__t->next;\
				k_delete(__t);\
				break;\
			}\
			__v=__t;\
			__t=__t->next;\
		}\
		*(ptrptr)=__r;\
	}K_STMT_END

#define k_slist_remove_link(name, p, link, ptrptr)\
	K_STMT_BEGIN{\
		name* __r=(p);\
		name* __t=(p);\
		name* __v=NULL;\
		while (__t)\
		{\
			if (__t==(link))\
			{\
				if (__v)\
					__v->next=__t->next;\
				if (__r==__t)\
					__r=__r->next;\
				__t->next=NULL;\
				break;\
			}\
			__v=__t;\
			__t=__t->next;\
		}\
		k_delete(link);\
		*(ptrptr)=__r;\
	}K_STMT_END

#define k_slist_copy(name, p, ptrptr)\
	K_STMT_BEGIN{\
		if ((p)==NULL)\
			*(ptrptr)=NULL;\
		else\
		{\
			name* __p;\
			name* __n;\
			name* __l;\
			__n=k_new_0(name);\
			__n->data=(p)->data;\
			__l=__n;\
			__p=(p)->next;\
			while (__p)\
			{\
				__l->next=k_new_1(name);\
				__l=__l->next;\
				__l->data=__p->data;\
				__p=__p->next;\
			}\
			__l->next=NULL;\
			*(ptrptr)=__n;\
		}\
	}K_STMT_END

#define k_slist_contains(name,p,item,ptrptr)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			if (__p->data==item)\
				break;\
			__p=__p->next;\
		}\
		*(ptrptr)=__p;\
	}K_STMT_END

#define k_slist_contains_func(name,p,func2,item,ptrptr)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			if (func2(__p->data, item))\
				break;\
			__p=__p->next;\
		}\
		*(ptrptr)=__p;\
	}K_STMT_END

#define k_slist_foreach(name,p,func_2,userdata)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			name* __n=__p->next;\
			func_2(userdata, __p->data);\
			__p=__n;\
		}\
	}K_STMT_END

#define k_slist_loopeach(name,p,func_1)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			name* __n=__p->next;\
			func_1(__p->data);\
			__p=__n;\
		}\
	}K_STMT_END

K_INLINE kpointer k_slist_inl_last(kpointer ptr)
{
	kSlist* p=(kSlist*)ptr;
	if (p)
	{
		while (p->next)
			p=p->next;
	}
	return p;
}

K_INLINE kpointer k_slist_inl_nth(kpointer ptr, ksize_t nth)
{
	kSlist* p=(kSlist*)ptr;
	while (nth-->0 && p)
		p=p->next;
	return (kpointer)p;
}

K_INLINE ksize_t k_slist_inl_count(kpointer ptr)
{
	kSlist* p=(kSlist*)ptr;
	ksize_t n=0;
	while (p)
	{
		n++;
		p=p->next;
	}
	return n;
}


//////////////////////////////////////////////////////////////////////////
// pointer solo list
K_SLIST_DECL(kPtrSlist, kpointer);

#define k_pslist_last(p)\
	k_slist_last(p)
	
#define k_pslist_nth(p, nth)\
	k_slist_nth(p, nth)
	
#define k_pslist_data(p, nth)\
	k_slist_data(p, nth)
	
#define k_pslist_count(p)\
	k_slist_count(p)

K_INLINE kPtrSlist* k_pslist_delete(kPtrSlist* p)
{
	k_slist_delete(kPtrSlist, p, &p);
	return p;
}

K_INLINE void k_pslist_disp(kPtrSlist* p, void (*func_1)(kpointer))
{
	if (!func_1)
	{
		k_slist_disp(kPtrSlist, p);
	}
	else
	{
		kPtrSlist* n;
		for (; p; p=n)
		{
			n=p->next;
			if (func_1)
				func_1(p->data);
			k_delete(p);
		}
	}
}

K_INLINE kPtrSlist* k_pslist_concat(kPtrSlist* p1, kPtrSlist* p2)
{
	k_slist_concat(kPtrSlist, p1, p2, &p1);
	return p1;
}

K_INLINE kPtrSlist* k_pslist_append(kPtrSlist* p, kpointer item)
{
	k_slist_append(kPtrSlist, p, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_prepend(kPtrSlist* p, kpointer item)
{
	k_slist_prepend(kPtrSlist, p, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_insert(kPtrSlist* p, kPtrSlist* sib, kpointer item)
{
	k_slist_insert(kPtrSlist, p, sib, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_insert_nth(kPtrSlist* p, kint nth, kpointer item)
{
	k_slist_insert_nth(kPtrSlist, p, nth, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_remove(kPtrSlist* p, kpointer item)
{
	k_slist_remove(kPtrSlist, p, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_remove_link(kPtrSlist* p, kPtrSlist* link)
{
	k_slist_remove_link(kPtrSlist, p, link, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_copy(kPtrSlist* p)
{
	kPtrSlist* n;
	k_slist_copy(kPtrSlist, p, &n);
	return n;
}

K_INLINE kPtrSlist* k_pslist_contains(kPtrSlist* p, kpointer item)
{
	k_slist_contains(kPtrSlist, p, item, &p);
	return p;
}

#define k_pslist_foreach(p,func_2,userdata)\
	k_slist_foreach(kPtrSlist, p, func_2, userdata)

#define k_pslist_loopeach(p,func_1)\
	k_slist_LoopEach(kPtrSlist, p, func_1);


//////////////////////////////////////////////////////////////////////////
// fixed slice
typedef struct kSlice
{
	kbyte*				data;
	ksize_t				max;
	ksize_t				count;
} kSlice;

#define K_SLICE_DECL(name, type)\
	typedef type name##Type;\
	typedef struct name { type* data; ksize_t max; ksize_t count; } name

#define k_slice_nth(p,n)				(((p)->data)[(ksize_t)(n)])
#define k_slice_invat(p,n)				(((p)->data)[((p)->count-1-(ksize_t)(n)])
#define k_slice_count(p)				((p)->count)
#define k_slice_maximum(p)				((p)->max)
#define k_slice_data(p)					((p)->data)
#define k_slice_sizeof(name)			(sizeof(name##Type))
#define k_slice_is_empty(p)				((p)->count==0)
#define k_slice_is_have(p)				((p)->count!=0)

#define k_slice_test_init(name,p,_max)\
	K_STMT_BEGIN{\
		k_assert((p)->data==NULL && (p)->max==0 && (p)->count==0, "uninitialized slice memory.");\
		(p)->data=k_new(_max, name##Type);\
		(p)->max=_max;\
	}K_STMT_END

#define k_slice_init(name,p,_max)\
	K_STMT_BEGIN{\
		(p)->max=_max;\
		(p)->count=0;\
		(p)->data=k_new((p)->max, name##Type);\
	}K_STMT_END

#define k_slice_disp(name,p)\
	K_STMT_BEGIN{ k_delete((p)->data); }K_STMT_END

#define k_slice_clear(name,p)\
	K_STMT_BEGIN{ (p)->count=0; }K_STMT_END

#define k_slice_disable(name,p)\
	K_STMT_BEGIN{ (p)->max=(p)->count; }K_STMT_END

#define k_slice_expand(name,p,newmax)\
	K_STMT_BEGIN{\
		if ((p)->count>(newmax))\
			(p)->count=(newmax);\
		(p)->data=k_renew((p)->data, newmax, name##Type);\
		(p)->max=(newmax);\
	}K_STMT_END

#define k_slice_push(name,p,itemref,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==(p)->max)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			(p)->data[(p)->count]=*(itemref);\
			(p)->count++;\
		}\
	}K_STMT_END

#define k_slice_pop(name,p,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==0)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else if ((p)->count==1)\
		{\
			if (__r) *__r=TRUE;\
			(p)->count=0;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			(p)->count--;\
			(p)->data[0]=(p)->data[(p)->count];\
		}\
	}K_STMT_END

#define k_slice_pop_value(name,p,retvalueref,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==0)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else if ((p)->count==1)\
		{\
			if (__r) *__r=TRUE;\
			*(retvalueref)=(p)->data[0];\
			(p)->count=0;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			*(retvalueref)=(p)->data[0];\
			(p)->count--;\
			(p)->data[0]=(p)->data[(p)->count];\
		}\
	}K_STMT_END

#define k_slice_find(name,p,start,func2,userdata,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=(ksize_t)(start); __i<__cnt; __i++)\
		{\
			if (func2(userdata, &k_slice_nth(p,__i)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_contains(name,p,itemptr,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (memcmp(&k_slice_nth(p,__i), itemptr, sizeof(name##Type))==0)\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_contains_func(name,p,func,itemptr,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (func(&k_slice_nth(p,__i),(itemptr)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, &k_slice_nth(p,__i));\
	}K_STMT_END

#define k_slice_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(&k_slice_nth(p,__i));\
	}K_STMT_END

#define k_slice_ptr_push(name,p,item,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==(p)->max)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			(p)->data[(p)->count]=(item);\
			(p)->count++;\
		}\
	}K_STMT_END

#define k_slice_ptr_pop(name,p,retchamref)\
	k_slice_Pop(name,p,retchamref)

#define k_slice_ptr_pop_value(name,p,retvalueref)\
	K_STMT_BEGIN{\
		if ((p)->count==0)\
		{\
			*(retvalueref)=NULL;\
		}\
		else if ((p)->count==1)\
		{\
			*(retvalueref)=(p)->data[0];\
			(p)->count=0;\
		}\
		else\
		{\
			*(retvalueref)=(p)->data[0];\
			(p)->count--;\
			(p)->data[0]=(p)->data[(p)->count];\
		}\
	}K_STMT_END


#define k_slice_ptr_find(name,p,start,func2,userdata,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=(ksize_t)(start); __i<__cnt; __i++)\
		{\
			if (func2(userdata, k_slice_nth(p,__i)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_ptr_contains(name,p,item,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (k_slice_nth(p,__i)==item)\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_ptr_contains_func(name,p,func,item,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (func(k_slice_nth(p,__i),(item)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_ptr_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, k_slice_nth(p,__i));\
	}K_STMT_END

#define k_slice_ptr_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(k_slice_nth(p,__i));\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// hash
typedef struct kHashNode
{
	struct kHashNode*	sib;
	struct kHashNode*	next;
	struct kHashNode*	prev;
	ksize_t				hash;
	kuintptr			key;
	kuintptr			value;
} kHashNode;

typedef struct kHash
{
	ksize_t				revision;
	ksize_t				bucket;
	ksize_t				count;
	struct kHashNode**	nodes;
	struct kHashNode*	frst;
	struct kHashNode*	last;
} kHash;

#define K_HASH_DECL(name,keytype,valuetype)\
	typedef keytype name##Key;\
	typedef valuetype name##Value;\
	typedef struct name##Node { struct name##Node* sib; struct name##Node* next; struct name##Node* prev; ksize_t hash; name##Key key; name##Value value; } name##Node;\
	typedef struct name { ksize_t revision; ksize_t bucket; ksize_t count; struct name##Node** nodes; struct name##Node* frst; struct name##Node* last; } name

#define K_HASH_HASH(name,func1)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(name##Key* key) { return func1(key); }
#define K_HASH_HASH_PURE(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(name##Key* key) { return K_CAST_PTR_TO_UINT(*key); }

#define K_HASH_EQ(name,func2)\
	K_INLINE kcham name##_Hash_Cb_Eq(name##Key* k1, name##Key* k2) { return func2(k1, k2); }
#define K_HASH_EQ_PURE(name)\
	K_INLINE kcham name##_Hash_Cb_Eq(name##Key* k1, name##Key* k2) { return *k1==*k2; }

#define K_HASH_KEY(name,func1)\
	K_INLINE void name##_Hash_Cb_Key(name##Key* key) { func1(key); }
#define K_HASH_KEY_DELETE(name)\
	K_INLINE void name##_Hash_Cb_Key(name##Key* key) { k_delete(*key); }
#define K_HASH_KEY_NONE(name)\
	K_INLINE void name##_Hash_Cb_Key(name##Key* key) { (void)key; }

#define K_HASH_VALUE(name,func1)\
	K_INLINE void name##_Hash_Cb_Value(name##Value* value) { func1(value); }
#define K_HASH_VALUE_DELETE(name)\
	K_INLINE void name##_Hash_Cb_Value(name##Value* value) { k_delete(*value); }
#define K_HASH_VALUE_NONE(name)\
	K_INLINE void name##_Hash_Cb_Value(name##Value* value) { (void)value; }

#define K_HASH_BOTH_NONE(name)\
	K_HASH_KEY_NONE(name);\
	K_HASH_VALUE_NONE(name)

#define K_HASH_HASHER_INT(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kint* key) { return K_CAST_INT_TO_UINT(*key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(kint* k1, kint* k2) { return (*k1)==(*k2); }
#define K_HASH_HASHER_UINT(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kuint* key) { return *key; }\
	K_INLINE kcham name##_Hash_Cb_Eq(kuint* k1, kuint* k2) { return ((kint)*k1)==((kint)*k2); }
#define K_HASH_HASHER_SIZET(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(ksize_t* key) { return (kuintptr)*key; }\
	K_INLINE kcham name##_Hash_Cb_Eq(ksize_t* k1, ksize_t* k2) { return (*k1)==(*k2); }
#define K_HASH_HASHER_CHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kconstpointer key) { return k_strhash(*(const char**)key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(kconstpointer k1, kconstpointer k2) { return k_strcmp(*(const char**)k1, *(const char**)k2)==0; }
#define K_HASH_HASHER_WCHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kconstpointer key) { return k_wcshash(*(const kwchar**)key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(kconstpointer k1, kconstpointer k2) { return k_wcscmp(*(const kwchar**)k1, *(const kwchar**)k2)==0; }
#define K_HASH_HASHER_CHAR_PTR_INCASE(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(const char** key) { return k_strihash(*key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(const char** k1, const char** k2) { return k_stricmp(*k1, *k2)==0; }
#define K_HASH_HASHER_WCHAR_PTR_INCASE(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(const kwchar** key) { return k_wcsihash(*key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(const kwchar** k1, const kwchar** k2) { return k_wcsicmp(*k1, *k2)==0; }

#define K_HASH_PTR_HASH(name,func1)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(name##Key key) { return func1(key); }
#define K_HASH_PTR_HASH_PURE(name)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(name##Key key) { return K_CAST_PTR_TO_SIZE(key); }

#define K_HASH_PTR_EQ(name,func2)\
	K_INLINE kcham name##_Hash_Cb_PtrEq(name##Key k1, name##Key k2) { return func2(k1, k2); }
#define K_HASH_PTR_EQ_PURE(name)\
	K_INLINE kcham name##_Hash_Cb_PtrEq(name##Key k1, name##Key k2) { return k1==k2; }

#define K_HASH_PTR_KEY(name,func1)\
	K_INLINE void name##_Hash_Cb_PtrKey(name##Key key) { func1(key); }
#define K_HASH_PTR_KEY_DELETE(name)\
	K_INLINE void name##_Hash_Cb_PtrKey(name##Key key) { k_delete(key); }
#define K_HASH_PTR_KEY_NONE(name)\
	K_INLINE void name##_Hash_Cb_PtrKey(name##Key key) { (void)key; }

#define K_HASH_PTR_VALUE(name,func1)\
	K_INLINE void name##_Hash_Cb_PtrValue(name##Value value) { func1(value); }
#define K_HASH_PTR_VALUE_DELETE(name)\
	K_INLINE void name##_Hash_Cb_PtrValue(name##Value value) { k_delete(value); }
#define K_HASH_PTR_VALUE_NONE(name)\
	K_INLINE void name##_Hash_Cb_PtrValue(name##Value value) { (void)value; }

#define K_HASH_PTR_BOTH_NONE(name)\
	K_HASH_PTR_KEY_NONE(name);\
	K_HASH_PTR_VALUE_NONE(name)

#define K_HASH_PTR_HASHER_CHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(const char* key) { return k_strhash(key); }\
	K_INLINE kcham name##_Hash_Cb_PtrEq(const char* k1, const char* k2) { return k_strcmp(k1, k2)==0; }
#define K_HASH_PTR_HASHER_WCHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(const kwchar* key) { return k_wcshash(key); }\
	K_INLINE kcham name##_Hash_Cb_PtrEq(const kwchar* k1, const kwchar* k2) { return k_wcscmp(k1, k2)==0; }

//
#define k_hash_count(p)					((p)->count)
#define k_hash_bucket(p)				((p)->bucket)
#define k_hash_revision(p)				((p)->revision)
#define k_hash_node_first(p)			((p)->last)
#define k_hash_node_last(p)				((p)->frst)

#define k_hash_init(name,p)\
	K_STMT_BEGIN{\
		(p)->revision=0;\
		(p)->count=0;\
		(p)->bucket=K_MIN_HASH;\
		(p)->nodes=k_new_zero(K_MIN_HASH, struct name##Node*);\
		(p)->frst=(p)->last=NULL;\
	}K_STMT_END

//
#define k_hash_disp(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			name##_Hash_Cb_Key(&__node->key);\
			name##_Hash_Cb_Value(&__node->value);\
			k_delete(__node);\
		}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_hash_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_hash_inl_erase_node(name,p,&__en);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_clear(name,p)\
	K_STMT_BEGIN{\
		k_hash_inl_erase_all(name,p);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func3(userdata, &__node->key, &__node->value);\
	}K_STMT_END

#define k_hash_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(&__node->key, &__node->value);\
	}K_STMT_END

#define k_hash_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(userdata, &__node->value);\
	}K_STMT_END

#define k_hash_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func1(&__node->value);\
	}K_STMT_END

#define k_hash_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_hash_inl_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_hash_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_hash_inl_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? &__node->value : NULL;\
	}K_STMT_END

#define k_hash_add(name,p,keyptr,valueptr)\
	k_hash_inl_set(name,p,keyptr,valueptr,FALSE)

#define k_hash_set(name,p,keyptr,valueptr)\
	k_hash_inl_set(name,p,keyptr,valueptr,TRUE);

#define k_hash_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_hash_inl_erase(name,p,keyptr,retcham_can_be_null);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_find(name,p,func,userdata,retkey,gotoname)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
		{\
			if (func(userdata, &__node->key, &__node->value))\
			{\
				retkey=&__node->key;\
				goto K_CONCAT(pos_hash_find_exit,gotoname);\
			}\
		}\
		retkey=NULL;\
		K_CONCAT(pos_hash_find_exit,gotoname):;\
	}K_STMT_END

//
#define k_hash_inl_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_hash_inl_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_hash_inl_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_hash_inl_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_Key(&__ann->key);\
				__ann->key=*(keyptr);\
				name##_Hash_Cb_Value(&__ann->value);\
				__ann->value=*(valueptr);\
			}\
			else\
			{\
				name##_Hash_Cb_Key(keyptr);\
				name##_Hash_Cb_Value(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=*(keyptr);\
			__ann->value=*(valueptr);\
			/* step 2*/\
			if ((p)->frst)\
				(p)->frst->prev=__ann;\
			else\
				(p)->last=__ann;\
			__ann->next=(p)->frst;\
			__ann->prev=NULL;\
			(p)->frst=__ann;\
			/* step 3 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 4 */\
			k_hash_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_hash_inl_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_hash_inl_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_hash_inl_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_hash_inl_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		if (__enn->next)\
			__enn->next->prev=__enn->prev;\
		else\
		{\
			k_assert_eq((p)->last, __enn);\
			(p)->last=__enn->prev;\
		}\
		if (__enn->prev)\
			__enn->prev->next=__enn->next;\
		else\
		{\
			k_assert_eq((p)->frst, __enn);\
			(p)->frst=__enn->next;\
		}\
		/* step3 */\
		name##_Hash_Cb_Key(&__enn->key);\
		name##_Hash_Cb_Value(&__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_hash_inl_erase_all(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __enn;\
		struct name##Node* __enx;\
		for (__enn=(p)->frst; __enn; __enn=__enx)\
		{\
			__enx=__enn->next;\
			name##_Hash_Cb_Key(&__enn->key);\
			name##_Hash_Cb_Value(&__enn->value);\
			k_delete(__enn);\
		}\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

//
#define k_hash_ptr_disp(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			name##_Hash_Cb_PtrKey(__node->key);\
			name##_Hash_Cb_PtrValue(__node->value);\
			k_delete(__node);\
		}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_hash_ptr_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_hash_inl_ptr_erase_node(name,p,&__en);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_ptr_clear(name,p)\
	K_STMT_BEGIN{\
		k_hash_inl_ptr_erase_all(name,p);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_ptr_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func3(userdata, __node->key, __node->value);\
	}K_STMT_END

#define k_hash_ptr_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(__node->key, __node->value);\
	}K_STMT_END

#define k_hash_ptr_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(userdata, __node->value);\
	}K_STMT_END

#define k_hash_ptr_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func1(__node->value);\
	}K_STMT_END

#define k_hash_ptr_loopeach_inv_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
			func1(__node->value);\
	}K_STMT_END

#define k_hash_ptr_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_hash_inl_ptr_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_hash_ptr_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_hash_inl_ptr_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? __node->value : NULL;\
	}K_STMT_END

#define k_hash_ptr_add(name,p,keyptr,valueptr)\
	k_hash_inl_ptr_set(name,p,keyptr,valueptr,FALSE)

#define k_hash_ptr_set(name,p,keyptr,valueptr)\
	k_hash_inl_ptr_set(name,p,keyptr,valueptr,TRUE);

#define k_hash_ptr_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_hash_inl_ptr_erase(name,p,keyptr,retcham_can_be_null);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

//
#define k_hash_inl_ptr_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_hash_inl_ptr_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_hash_inl_ptr_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_hash_inl_ptr_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_PtrKey(__ann->key);\
				__ann->key=keyptr;\
				name##_Hash_Cb_PtrValue(__ann->value);\
				__ann->value=valueptr;\
			}\
			else\
			{\
				name##_Hash_Cb_PtrKey(keyptr);\
				name##_Hash_Cb_PtrValue(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=keyptr;\
			__ann->value=valueptr;\
			/* step 2*/\
			if ((p)->frst)\
				(p)->frst->prev=__ann;\
			else\
				(p)->last=__ann;\
			__ann->next=(p)->frst;\
			__ann->prev=NULL;\
			(p)->frst=__ann;\
			/* step 3 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 4 */\
			k_hash_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_hash_inl_ptr_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_hash_inl_ptr_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_hash_inl_ptr_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_hash_inl_ptr_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		if (__enn->next)\
			__enn->next->prev=__enn->prev;\
		else\
		{\
			k_assert_eq((p)->last, __enn);\
			(p)->last=__enn->prev;\
		}\
		if (__enn->prev)\
			__enn->prev->next=__enn->next;\
		else\
		{\
			k_assert_eq((p)->frst, __enn);\
			(p)->frst=__enn->next;\
		}\
		/* step3 */\
		name##_Hash_Cb_PtrKey(__enn->key);\
		name##_Hash_Cb_PtrValue(__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_hash_inl_ptr_erase_all(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __enn;\
		struct name##Node* __enx;\
		for (__enn=(p)->frst; __enn; __enn=__enx)\
		{\
			__enx=__enn->next;\
			name##_Hash_Cb_PtrKey(__enn->key);\
			name##_Hash_Cb_PtrValue(__enn->value);\
			k_delete(__enn);\
		}\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

//
#define k_hash_inl_test_size(name,p)\
	K_STMT_BEGIN{\
		ksize_t __cnt=(p)->count;\
		ksize_t __bkt=(p)->bucket;\
		if ((__bkt>=3*__cnt && __bkt>K_MIN_HASH) ||\
			(3*__bkt<=__cnt && __bkt<K_MAX_HASH))\
			k_hash_inl_resize((kHash*)p);\
	}K_STMT_END

K_INLINE void k_hash_inl_resize(kHash* p)
{
	ksize_t i, newbucket;
	kHashNode** newnodes;

	newbucket=k_primeclose(p->count);
	newbucket=K_CLAMP(newbucket, K_MIN_HASH, K_MAX_HASH);
	newnodes=k_new_zero(newbucket, kHashNode*);

	for (i=0; i<p->bucket; i++)
	{
		kHashNode* node;
		kHashNode* next;
		ksize_t hashmask;
		for (node=p->nodes[i]; node; node=next)
		{
			next=node->sib;
			hashmask=node->hash%newbucket;
			node->sib=newnodes[hashmask];
			newnodes[hashmask]=node;
		}
	}

	k_delete(p->nodes);
	p->nodes=newnodes;
	p->bucket=newbucket;
}


//////////////////////////////////////////////////////////////////////////
// mukum
typedef struct kMukumNode
{
	struct kMukumNode*	sib;
	ksize_t				hash;
	kuintptr			key;
	kuintptr			value;
} kMukumNode;

typedef struct kMukum
{
	ksize_t				revision;
	ksize_t				bucket;
	ksize_t				count;
	kMukumNode**		nodes;
} kMukum;

#define K_MUKUM_DECL(name,keytype,valuetype)\
	typedef keytype name##Key;\
	typedef valuetype name##Value;\
	typedef struct name##Node { struct name##Node* sib; ksize_t hash; name##Key key; name##Value value; } name##Node;\
	typedef struct name { ksize_t revision; ksize_t bucket; ksize_t count; struct name##Node** nodes; } name

#define K_MUKUM_HASH(name,func1)				K_HASH_HASH(name,func1)
#define K_MUKUM_HASH_PURE(name)					K_HASH_HASH_PURE(name)

#define K_MUKUM_EQ(name,func2)					K_HASH_EQ(name,func2)
#define K_MUKUM_EQ_PURE(name)					K_HASH_EQ_PURE(name)

#define K_MUKUM_KEY(name,func1)					K_HASH_KEY(name,func1)
#define K_MUKUM_KEY_DELETE(name)				K_HASH_KEY_DELETE(name)
#define K_MUKUM_KEY_NONE(name)					K_HASH_KEY_NONE(name)

#define K_MUKUM_VALUE(name,func1)				K_HASH_VALUE(name,func1)
#define K_MUKUM_VALUE_DELETE(name)				K_HASH_VALUE_DELETE(name)
#define K_MUKUM_VALUE_NONE(name)				K_HASH_VALUE_NONE(name))

#define K_MUKUM_BOTH_NONE(name)					K_HASH_BOTH_NONE(name)

#define K_MUKUM_HASHER_INT(name)				K_HASH_HASHER_INT(name)
#define K_MUKUM_HASHER_UINT(name)				K_HASH_HASHER_UINT(name)
#define K_MUKUM_HASHER_CHAR_PTR(name)			K_HASH_HASHER_CHAR_PTR(name)
#define K_MUKUM_HASHER_WCHAR_PTR(name)			K_HASH_HASHER_WCHAR_PTR(name)
#define K_MUKUM_HASHER_CHAR_PTR_INCASE(name)	K_HASH_HASHER_CHAR_PTR_INCASE(name)
#define K_MUKUM_HASHER_WCHAR_PTR_INCASE(name)	K_HASH_HASHER_WCHAR_PTR_INCASE(name)

#define K_MUKUM_PTR_HASH(name,func1)			K_HASH_PTR_HASH(name,func1)
#define K_MUKUM_PTR_HASH_PURE(name)				K_HASH_PTR_HASH_PURE(name)

#define K_MUKUM_PTR_EQ(name,func2)				K_HASH_PTR_EQ(name,func2)
#define K_MUKUM_PTR_EQ_PURE(name)				K_HASH_PTR_EQ_PURE(name)

#define K_MUKUM_PTR_KEY(name,func1)				K_HASH_PTR_KEY(name,func1)
#define K_MUKUM_PTR_KEY_DELETE(name)			K_HASH_PTR_KEY_DELETE(name)
#define K_MUKUM_PTR_KEY_NONE(name)				K_HASH_PTR_KEY_NONE(name)

#define K_MUKUM_PTR_VALUE(name,func1)			K_HASH_PTR_VALUE(name,func1)
#define K_MUKUM_PTR_VALUE_DELETE(name)			K_HASH_PTR_VALUE_DELETE(name)
#define K_MUKUM_PTR_VALUE_NONE(name)			K_HASH_PTR_VALUE_NONE(name)

#define K_MUKUM_PTR_BOTH_NONE(name)				K_HASH_PTR_BOTH_NONE(name)

#define K_MUKUM_PTR_HASHER_CHAR_PTR(name)		K_HASH_PTR_HASHER_CHAR_PTR(name)
#define K_MUKUM_PTR_HASHER_WCHAR_PTR(name)		K_HASH_PTR_HASHER_WCHAR_PTR(name)

//
#define k_mukum_count(p)					((p)->count)
#define k_mukum_bucket(p)					((p)->bucket)
#define k_mukum_revision(p)					((p)->revision)

#define k_mukum_init(name,p)\
	K_STMT_BEGIN{\
		(p)->revision=0;\
		(p)->count=0;\
		(p)->bucket=K_MIN_HASH;\
		(p)->nodes=k_new_zero(K_MIN_HASH, struct name##Node*);\
	}K_STMT_END

//
#define k_mukum_disp(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_Key(&__node->key);\
				name##_Hash_Cb_Value(&__node->value);\
				k_delete(__node);\
			}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_mukum_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_mukum_inl_erase_node(name,p,&__en);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_clear(name,p)\
	K_STMT_BEGIN{\
		k_mukum_inl_erase_all(name,p);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func3(userdata, &__node->key, &__node->value);\
	}K_STMT_END

#define k_mukum_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(&__node->key, &__node->value);\
	}K_STMT_END

#define k_mukum_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(userdata, &__node->value);\
	}K_STMT_END

#define k_mukum_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func1(&__node->value);\
	}K_STMT_END

// value type
#define k_mukum_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_mukum_inl_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_mukum_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_mukum_inl_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? &__node->value : NULL;\
	}K_STMT_END

#define k_mukum_add(name,p,keyptr,valueptr)\
	k_mukum_inl_set(name,p,keyptr,valueptr,FALSE);

#define k_mukum_set(name,p,keyptr,valueptr)\
	k_mukum_inl_set(name,p,keyptr,valueptr,TRUE);\

#define k_mukum_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_mukum_inl_erase(name,p,keyptr,retcham_can_be_null);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_find(name,p,func,userdata,retkey,gotoname)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
		{\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
			{\
				if (func(userdata, &__node->key, &__node->value))\
				{\
					retkey=&__node->key;\
					goto K_CONCAT(pos_mukum_find_exit,gotoname);\
				}\
			}\
		}\
		retkey=NULL;\
	K_CONCAT(pos_mukum_find_exit,gotoname):;\
	}K_STMT_END

//
#define k_mukum_inl_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_mukum_inl_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_mukum_inl_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_mukum_inl_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_Key(&__ann->key);\
				__ann->key=*(keyptr);\
				name##_Hash_Cb_Value(&__ann->value);\
				__ann->value=*(valueptr);\
			}\
			else\
			{\
				name##_Hash_Cb_Key(keyptr);\
				name##_Hash_Cb_Value(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=*(keyptr);\
			__ann->value=*(valueptr);\
			/* step 2 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 3 */\
			k_mukum_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_mukum_inl_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_mukum_inl_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_mukum_inl_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_mukum_inl_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		name##_Hash_Cb_Key(&__enn->key);\
		name##_Hash_Cb_Value(&__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_mukum_inl_erase_all(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_Key(&__node->key);\
				name##_Hash_Cb_Value(&__node->value);\
				k_delete(__node);\
			}\
		(p)->count=0;\
		(p)->revision++;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

// 
#define k_mukum_ptr_disp(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_PtrKey(__node->key);\
				name##_Hash_Cb_PtrValue(__node->value);\
				k_delete(__node);\
			}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_mukum_ptr_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_mukum_inl_ptr_erase_node(name,p,&__en);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_ptr_clear(name,p)\
	K_STMT_BEGIN{\
		k_mukum_inl_ptr_erase_all(name,p);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_ptr_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func3(userdata, __node->key, __node->value);\
	}K_STMT_END

#define k_mukum_ptr_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(__node->key, __node->value);\
	}K_STMT_END

#define k_mukum_ptr_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(userdata, __node->value);\
	}K_STMT_END

#define k_mukum_ptr_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func1(__node->value);\
	}K_STMT_END

// value type
#define k_mukum_ptr_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_mukum_inl_ptr_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_mukum_ptr_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_mukum_inl_ptr_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? __node->value : NULL;\
	}K_STMT_END

#define k_mukum_ptr_add(name,p,keyptr,valueptr)\
	k_mukum_inl_ptr_set(name,p,keyptr,valueptr,FALSE)

#define k_mukum_ptr_set(name,p,keyptr,valueptr)\
	k_mukum_inl_ptr_set(name,p,keyptr,valueptr,TRUE)

#define k_mukum_ptr_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_mukum_inl_ptr_erase(name,p,keyptr,retcham_can_be_null);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_ptr_find(name,p,func,userdata,retkey,gotoname)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
		{\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
			{\
				if (func(userdata, __node->key, __node->value))\
				{\
					*(retkey)=__node->key;\
					goto K_CONCAT(pos_mukum_find_exit,gotoname);\
				}\
			}\
		}\
		retkey=NULL;\
		K_CONCAT(pos_mukum_find_exit,gotoname):;\
	}K_STMT_END

//
#define k_mukum_inl_ptr_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_mukum_inl_ptr_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_mukum_inl_ptr_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_mukum_inl_ptr_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_PtrKey(__ann->key);\
				__ann->key=keyptr;\
				name##_Hash_Cb_PtrValue(__ann->value);\
				__ann->value=valueptr;\
			}\
			else\
			{\
				name##_Hash_Cb_PtrKey(keyptr);\
				name##_Hash_Cb_PtrValue(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=keyptr;\
			__ann->value=valueptr;\
			/* step 2 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 3 */\
			k_mukum_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_mukum_inl_ptr_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_mukum_inl_ptr_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_mukum_inl_ptr_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_mukum_inl_ptr_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		name##_Hash_Cb_PtrKey(__enn->key);\
		name##_Hash_Cb_PtrValue(__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_mukum_inl_ptr_erase_all(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_PtrKey(__node->key);\
				name##_Hash_Cb_PtrValue(__node->value);\
				k_delete(__node);\
			}\
		(p)->count=0;\
		(p)->revision++;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

//
#define k_mukum_inl_test_size(name,p)\
	K_STMT_BEGIN{\
		ksize_t __cnt=(p)->count;\
		ksize_t __bkt=(p)->bucket;\
		if ((__bkt>=3*__cnt && __bkt>K_MIN_HASH) ||\
			(3*__bkt<=__cnt && __bkt<K_MAX_HASH))\
			k_mukum_inl_resize((kMukum*)p);\
	}K_STMT_END

K_INLINE void k_mukum_inl_resize(kMukum* p)
{
	ksize_t i, newbucket;
	kMukumNode** newnodes;

	newbucket=k_primeclose(p->count);
	newbucket=K_CLAMP(newbucket, K_MIN_HASH, K_MAX_HASH);
	newnodes=k_new_zero(newbucket, kMukumNode*);

	for (i=0; i<p->bucket; i++)
	{
		kMukumNode* node;
		kMukumNode* next;
		ksize_t hashmask;
		for (node=p->nodes[i]; node; node=next)
		{
			next=node->sib;
			hashmask=node->hash%newbucket;
			node->sib=newnodes[hashmask];
			newnodes[hashmask]=node;
		}
	}

	k_delete(p->nodes);
	p->nodes=newnodes;
	p->bucket=newbucket;
}


//////////////////////////////////////////////////////////////////////////
// blue string
typedef struct kBstr
{
	kint				len;
	char				data[];
} kBstr;

typedef struct kBstr64
{
	kint				len;
	char				data[64];
} kBstr64;

typedef struct kBstr260
{
	kint				len;
	char				data[260];
} kBstr260;

typedef struct kBstr1k
{
	kint				len;
	char				data[1024];
} kBstr1k;

typedef struct kBstr2k
{
	kint				len;
	char				data[2048];
} kBstr2k;

typedef struct kBstr4k
{
	kint				len;
	char				data[4096];
} kBstr4k;

typedef struct kBstr8k
{
	kint				len;
	char				data[8192];
} kBstr8k;

#define k_bstr_length(p)				(((kBstr*)(p))->len)
#define k_bstr_data(p)					(((kBstr*)(p))->data)
#define k_bstr_nth(p,n)					(((kBstr*)(p))->data[(n)])
#define k_bstr_inv(p,n)					(((kBstr*)(p))->data[(((kBstr*)(p))->len)-(n)-1])

K_INLINE void k_bstr_test_init(kpointer p)
{
	k_assert_0(((kBstr*)p)->len==0 && *((kBstr*)p)->data=='\0');
	(void)p;
}

K_INLINE void k_bstr_init(kpointer p, const char* str)
{
	if (str)
	{
		((kBstr*)p)->len=(kint)k_strlen(str);
		k_strcpy(((kBstr*)p)->data, str);
	}
	else
	{
		((kBstr*)p)->len=0;
		((kBstr*)p)->data[0]='\0';
	}
}

K_INLINE void k_bstr_zero(kpointer p)
{
	((kBstr*)p)->len=0;
	((kBstr*)p)->data[0]='\0';
}

K_INLINE kcham k_bstr_eq(kpointer p1, kpointer p2)
{
	return k_strcmp(((kBstr*)p1)->data, ((kBstr*)p2)->data)==0;
}

K_INLINE kpointer k_bstr_test_len(kpointer p)
{
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
	return p;
}

K_INLINE kpointer k_bstr_clear(kpointer p)
{
	((kBstr*)p)->len=0;
	((kBstr*)p)->data[0]='\0';
	return p;
}

K_INLINE kpointer k_bstr_set(kpointer p, const char* str)
{
	((kBstr*)p)->len=(kint)k_strlen(str);
	k_strcpy(((kBstr*)p)->data, str);
	return p;
}

K_INLINE kpointer k_bstr_set_safe(kpointer p, const char* str, kint max)
{
	((kBstr*)p)->len=(kint)k_strlen(str);
	if (((kBstr*)p)->len<(max-1))
		k_strcpy(((kBstr*)p)->data, str);
	else
	{
		((kBstr*)p)->len=max-1;
		k_strncpy(((kBstr*)p)->data, str, max-1);
	}
	return p;
}

K_INLINE kpointer k_bstr_set_bls(kpointer p, kconstpointer right)
{
	((kBstr*)p)->len=((const kBstr*)right)->len;
	k_strcpy(((kBstr*)p)->data, ((const kBstr*)right)->data);
	return p;
}

K_INLINE kpointer k_bstr_set_len(kpointer p, const char* str, kint len)
{
	if (len<0)
		return k_bstr_set(p, str);
	else
	{
		((kBstr*)p)->len=len;
		k_strncpy(((kBstr*)p)->data, str, len);
		return p;
	}
}

K_INLINE kpointer k_bstr_set_char(kpointer p, char ch)
{
	((kBstr*)p)->len=1;
	((kBstr*)p)->data[0]=ch;
	((kBstr*)p)->data[1]='\0';
	return p;
}

K_INLINE kpointer k_bstr_set_rep(kpointer p, kint ch, kint cnt)
{
	((kBstr*)p)->len=(kint)k_strfll(((kBstr*)p)->data, 0, cnt, ch);
	((kBstr*)p)->data[cnt]='\0';
	return p;
}

K_INLINE kpointer k_bstr_append(kpointer p, const char* str)
{
	k_strcpy(&((kBstr*)p)->data[((kBstr*)p)->len], str);
	((kBstr*)p)->len+=(kint)k_strlen(str);
	return p;
}

K_INLINE kpointer k_bstr_append_bls(kpointer p, kconstpointer right)
{
	k_strcpy(&((kBstr*)p)->data[((kBstr*)p)->len], ((const kBstr*)right)->data);
	((kBstr*)p)->len+=((const kBstr*)right)->len;
	return p;
}

K_INLINE kpointer k_bstr_append_char(kpointer p, kint ch)
{
	((kBstr*)p)->data[((kBstr*)p)->len++]=(char)ch;
	((kBstr*)p)->data[((kBstr*)p)->len]='\0';
	return p;
}

K_INLINE kpointer k_bstr_append_rep(kpointer p, kint ch, kint cnt)
{
	((kBstr*)p)->len=(kint)k_strfll(((kBstr*)p)->data, ((kBstr*)p)->len, ((kBstr*)p)->len+cnt, ch);
	((kBstr*)p)->data[((kBstr*)p)->len]='\0';
	return p;
}

K_INLINE kcham k_bstr_is_empty(kconstpointer p)
{
	return ((const kBstr*)p)->len==0;
}

K_INLINE kcham k_bstr_is_have(kconstpointer p)
{
	return ((const kBstr*)p)->len!=0;
}

K_INLINE size_t k_bstr_hash(kconstpointer p, kcham igcase)
{
	return igcase ? k_strihash(((const kBstr*)p)->data) : k_strhash(((const kBstr*)p)->data);
}

K_INLINE kint k_bstr_compare(kconstpointer p, const char* s, kcham igcase)
{
	if (igcase)
		return k_stricmp(((const kBstr*)p)->data, s);
	else
		return k_strcmp(((const kBstr*)p)->data, s);
}

K_INLINE kint k_bstr_compare_bls(kconstpointer p1, kconstpointer p2, kcham igcase)
{
	if (igcase)
		return k_stricmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data);
	else
		return k_strcmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data);
}

K_INLINE kint k_bstr_compare_bls_length(kconstpointer p1, kconstpointer p2, kint len, kcham igcase)
{
	if (igcase)
		return k_strnicmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data, len);
	else
		return k_strncmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data, len);
}

K_INLINE void k_bstr_format(kpointer p, kint size, const char* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBstr*)p)->len=k_vsnprintf(((kBstr*)p)->data, size-1, fmt, va);
	va_end(va);
}

K_INLINE void k_bstr_format_va(kpointer p, kint size, const char* fmt, va_list va)
{
	((kBstr*)p)->len=k_vsnprintf(((kBstr*)p)->data, size-1, fmt, va);
}

K_INLINE void k_bstr_append_format(kpointer p, kint size, const char* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBstr*)p)->len+=k_vsnprintf(((kBstr*)p)->data+((kBstr*)p)->len, size-1-((kBstr*)p)->len, fmt, va);
	va_end(va);
}

K_INLINE void k_bstr_append_format_va(kpointer p, kint size, const char* fmt, va_list va)
{
	((kBstr*)p)->len+=k_vsnprintf(((kBstr*)p)->data+((kBstr*)p)->len, size-1-((kBstr*)p)->len, fmt, va);
}

K_INLINE kint k_bstr_has_char(kconstpointer p, const char* chars)
{
	char* s=k_strbrk(((kBstr*)p)->data, chars);
	return (s) ? (kint)(s-((kBstr*)p)->data) : -1;
}

K_INLINE kint k_bstr_find_char(kconstpointer p, int at, char ch)
{
	char* s=k_strchr(((kBstr*)p)->data+at, ch);
	return (s) ? (kint)(s-((kBstr*)p)->data) : -1;
}

K_INLINE kcham k_bstr_sub_bls(kpointer p, kconstpointer s, kint pos, kint len)
{
	k_return_value_if_fail(pos>=0, FALSE);
	k_return_value_if_fail(((const kBstr*)s)->len>=pos, FALSE);

	if (len>0)
	{
		k_return_value_if_fail(((const kBstr*)s)->len>=(pos+len), FALSE);
	}
	else
	{
		len=((const kBstr*)s)->len-pos;
	}

	k_strmid(((kBstr*)p)->data, ((const kBstr*)s)->data, pos, len);
	((kBstr*)p)->len=len;
	return TRUE;
}

K_INLINE void k_bstr_upper(kpointer p)
{
	k_strupr(((kBstr*)p)->data);
}

K_INLINE void k_bstr_lower(kpointer p)
{
	k_strlwr(((kBstr*)p)->data);
}

K_INLINE void k_bstr_trim(kpointer p)
{
	k_strtrim(((kBstr*)p)->data);
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
}

K_INLINE void k_bstr_trim_left(kpointer p)
{
	k_strltrim(((kBstr*)p)->data);
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
}

K_INLINE void k_bstr_trim_right(kpointer p)
{
	k_strrtrim(((kBstr*)p)->data);
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
}

K_INLINE void k_bstr_rem_chars(kpointer p, const char* rmlist)
{
	((kBstr*)p)->len=(kint)k_strlen(k_strrem(((kBstr*)p)->data, rmlist));
}

K_INLINE void k_bstr_intern(kpointer p)
{
	((kBstr*)p)->len = (kint)k_strlen(((kBstr*)p)->data);
}


//////////////////////////////////////////////////////////////////////////
// blue wcs
typedef struct kBwcs
{
	kint				len;
	kwchar				data[];
} kBwcs;

typedef struct kBwcs64
{
	kint				len;
	kwchar				data[64];
} kBwcs64;

typedef struct kBwcs260
{
	kint				len;
	kwchar				data[260];
} kBwcs260;

typedef struct kBwcs1k
{
	kint				len;
	kwchar				data[1024];
} kBwcs1k;

typedef struct kBwcs2k
{
	kint				len;
	kwchar				data[2048];
} kBwcs2k;

typedef struct kBwcs4k
{
	kint				len;
	kwchar				data[4096];
} kBwcs4k;

typedef struct kBwcs8k
{
	kint				len;
	kwchar				data[8192];
} kBwcs8k;

#define k_bwcs_length(p)				(((kBwcs*)(p))->len)
#define k_bwcs_data(p)					(((kBwcs*)(p))->data)
#define k_bwcs_nth(p,n)					(((kBwcs*)(p))->data[(n)])

K_INLINE void k_bwcs_test_init(kpointer p)
{
	k_assert_0(((kBwcs*)p)->len==0 && ((kBwcs*)p)->data[0]==L'\0');
	(void)p;
}

K_INLINE void k_bwcs_init(kpointer p, const kwchar* str)
{
	if (str)
	{
		((kBwcs*)p)->len=(kint)k_wcslen(str);
		k_wcscpy(((kBwcs*)p)->data, str);
	}
	else
	{
		((kBwcs*)p)->len=0;
		((kBwcs*)p)->data[0]=L'\0';
	}
}

K_INLINE void k_bwcs_zero(kpointer p)
{
	((kBwcs*)p)->len=0;
	((kBwcs*)p)->data[0]=L'\0';
}

K_INLINE kcham k_bwcs_eq(kpointer p1, kpointer p2)
{
	return k_wcscmp(((kBwcs*)p1)->data, ((kBwcs*)p2)->data)==0;
}

K_INLINE kpointer k_bwcs_test_len(kpointer p)
{
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
	return p;
}

K_INLINE kpointer k_bwcs_clear(kpointer p)
{
	((kBwcs*)p)->len=0;
	((kBwcs*)p)->data[0]=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_set(kpointer p, const kwchar* str)
{
	((kBwcs*)p)->len=(kint)k_wcslen(str);
	k_wcscpy(((kBwcs*)p)->data, str);
	return p;
}

K_INLINE kpointer k_bwcs_set_bls(kpointer p, kconstpointer right)
{
	((kBwcs*)p)->len=((const kBwcs*)right)->len;
	k_wcscpy(((kBwcs*)p)->data, ((const kBwcs*)right)->data);
	return p;
}

K_INLINE kpointer k_bwcs_set_len(kpointer p, const kwchar* str, kint len)
{
	if (len<0)
		return k_bwcs_set(p, str);
	else
	{
		((kBwcs*)p)->len=len;
		k_wcsncpy(((kBwcs*)p)->data, str, len);
		return p;
	}
}

K_INLINE kpointer k_bwcs_set_char(kpointer p, kwchar ch)
{
	((kBwcs*)p)->len=1;
	((kBwcs*)p)->data[0]=ch;
	((kBwcs*)p)->data[1]=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_set_rep(kpointer p, kint ch, kint cnt)
{
	((kBwcs*)p)->len=(kint)k_wcsfll(((kBwcs*)p)->data, 0, cnt, ch);
	((kBwcs*)p)->data[cnt]=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_append(kpointer p, const kwchar* str)
{
	k_wcscpy(&((kBwcs*)p)->data[((kBwcs*)p)->len], str);
	((kBwcs*)p)->len+=(kint)k_wcslen(str);
	return p;
}

K_INLINE kpointer k_bwcs_append_bls(kpointer p, kconstpointer right)
{
	k_wcscpy(&((kBwcs*)p)->data[((kBwcs*)p)->len], ((const kBwcs*)right)->data);
	((kBwcs*)p)->len+=((const kBwcs*)right)->len;
	return p;
}

K_INLINE kpointer k_bwcs_append_char(kpointer p, kwchar ch)
{
	((kBwcs*)p)->data[((kBwcs*)p)->len++]=(kwchar)ch;
	((kBwcs*)p)->data[((kBwcs*)p)->len]=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_append_rep(kpointer p, kint ch, kint cnt)
{
	((kBwcs*)p)->len=(kint)k_wcsfll(((kBwcs*)p)->data, ((kBwcs*)p)->len, ((kBwcs*)p)->len+cnt, ch);
	((kBwcs*)p)->data[((kBwcs*)p)->len]=L'\0';
	return p;
}

K_INLINE kcham k_bwcs_is_empty(kconstpointer p)
{
	return ((const kBwcs*)p)->len==0;
}

K_INLINE kcham k_bwcs_is_have(kconstpointer p)
{
	return ((const kBwcs*)p)->len!=0;
}

K_INLINE size_t k_bwcs_hash(kconstpointer p)
{
	return k_wcshash(((const kBwcs*)p)->data);
}

K_INLINE kint k_bwcs_compare(kconstpointer p, const kwchar* s, kcham igcase)
{
	if (igcase)
		return k_wcsicmp(((const kBwcs*)p)->data, s);
	else
		return k_wcscmp(((const kBwcs*)p)->data, s);
}

K_INLINE kint k_bwcs_compare_bls(kconstpointer p1, kconstpointer p2, kcham igcase)
{
	if (igcase)
		return k_wcsicmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data);
	else
		return k_wcscmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data);
}

K_INLINE kint k_bwcs_compare_bls_length(kconstpointer p1, kconstpointer p2, kint len, kcham igcase)
{
	if (igcase)
		return k_wcsnicmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data, len);
	else
		return k_wcsncmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data, len);
}

K_INLINE void k_bwcs_format(kpointer p, kint size, const kwchar* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBwcs*)p)->len=k_vsnwprintf(((kBwcs*)p)->data, size-1, fmt, va);
	va_end(va);
}

K_INLINE void k_bwcs_format_va(kpointer p, kint size, const kwchar* fmt, va_list va)
{
	((kBwcs*)p)->len=k_vsnwprintf(((kBwcs*)p)->data, size-1, fmt, va);
}

K_INLINE void k_bwcs_append_format(kpointer p, kint size, const kwchar* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBwcs*)p)->len+=k_vsnwprintf(((kBwcs*)p)->data+((kBwcs*)p)->len, size-1-((kBwcs*)p)->len, fmt, va);
	va_end(va);
}

K_INLINE void k_bwcs_append_format_va(kpointer p, kint size, const kwchar* fmt, va_list va)
{
	((kBwcs*)p)->len+=k_vsnwprintf(((kBwcs*)p)->data+((kBwcs*)p)->len, size-1-((kBwcs*)p)->len, fmt, va);
}

K_INLINE kint k_bwcs_has_char(kconstpointer p, const kwchar* kwchars)
{
	kwchar* s=k_wcsbrk(((kBwcs*)p)->data, kwchars);
	return (s) ? (kint)(s-((kBwcs*)p)->data) : -1;
}

K_INLINE kint k_bwcs_find_char(kconstpointer p, int at, kwchar ch)
{
	kwchar* s=k_wcschr(((kBwcs*)p)->data+at, ch);
	return (s) ? (kint)(s-((kBwcs*)p)->data) : -1;
}

K_INLINE kcham k_bwcs_sub_bls(kpointer p, kconstpointer s, kint pos, kint len)
{
	k_return_value_if_fail(pos>=0, FALSE);
	k_return_value_if_fail(((const kBwcs*)s)->len>=pos, FALSE);

	if (len>0)
	{
		k_return_value_if_fail(((const kBwcs*)s)->len>=(pos+len), FALSE);
	}
	else
	{
		len=((const kBwcs*)s)->len-pos;
	}

	k_wcsmid(((kBwcs*)p)->data, ((const kBwcs*)s)->data, pos, len);
	((kBwcs*)p)->len=len;
	return TRUE;
}

K_INLINE void k_bwcs_upper(kpointer p)
{
	k_wcsupr(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_lower(kpointer p)
{
	k_wcslwr(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_trim(kpointer p)
{
	k_wcstrim(((kBwcs*)p)->data);
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_trim_left(kpointer p)
{
	k_wcsltrim(((kBwcs*)p)->data);
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_trim_right(kpointer p)
{
	k_wcsrtrim(((kBwcs*)p)->data);
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_rem_chars(kpointer p, const kwchar* rmlist)
{
	((kBwcs*)p)->len=(kint)k_wcslen(k_wcsrem(((kBwcs*)p)->data, rmlist));
}

K_EXTERN_C_END





















#ifdef __cplusplus

//////////////////////////////////////////////////////////////////////////
// blue string
namespace tpl
{
	template <ksize_t SIZE>
	struct BlueStr
	{
		typedef BlueStr<SIZE> this_type;
		typedef kBstr cast_type;
		typedef char value_type;
		typedef const value_type* ConstIterator;
		typedef value_type* Iterator;

		int			_len;
		value_type	_data[SIZE];

		BlueStr()
		{
			k_bstr_zero(CastPtr());
		}

		BlueStr(const BlueStr& right)
		{
			k_bstr_set_bls(CastPtr(), right.CastPtr());
		}

		BlueStr(const value_type* str, kint len = -1)
		{
			k_bstr_set_len(CastPtr(), str, len);
		}

		BlueStr(value_type ch)
		{
			k_bstr_set_char(CastPtr, ch);
		}

		BlueStr& operator=(const BlueStr& right)
		{
			if (this != &right)
				k_bstr_set_bls(CastPtr(), right.CastPtr());
			return *this;
		}

		BlueStr& operator=(const value_type* right)
		{
			k_bstr_set(CastPtr(), right);
			return *this;
		}

		BlueStr& operator=(value_type right)
		{
			k_bstr_set_char(CastPtr(), right);
			return *this;
		}

		BlueStr& operator+=(const BlueStr& right)
		{
			k_bstr_append_bls(CastPtr(), right.CastPtr());
			return *this;
		}

		BlueStr& operator+=(const value_type* right)
		{
			k_bstr_append(CastPtr(), right);
			return *this;
		}

		BlueStr& operator+=(value_type ch)
		{
			k_bstr_append_char(CastPtr(), ch);
			return *this;
		}

		value_type operator[](kint index) const
		{
			return _data[index];
		}

		value_type operator[](kint index)
		{
			return _data[index];
		}

		const value_type* Data() const
		{
			return _data;
		}

		value_type* Data()
		{
			return _data;
		}

		kint Length() const
		{
			return _len;
		}

		ksize_t Size() const
		{
			return SIZE;
		}

		bool IsEmpty() const
		{
			return _len == 0;
		}

		bool IsHave() const
		{
			return _len > 0;
		}

		ksize_t GetHashCode(bool igcase = false) const
		{
			return k_bstr_hash(CastPtr(), igcase);
		}

		void Truncate(kint n)
		{
			_len = n;
			_data[n] = (value_type)0;
		}

		void Zero()
		{
			k_bstr_zero(CastPtr());
		}

		void Clear()
		{
			k_bstr_clear(CastPtr());
		}

		void Format(const value_type* fmt, ...)
		{
			va_list va;
			va_start(va, fmt);
			k_bstr_format_va(CastPtr(), SIZE, fmt, va);
			va_end(va);
		}

		void FormatVa(const value_type* fmt, va_list va)
		{
			k_bstr_format_va(CastPtr(), SIZE, fmt, va);
		}

		void AppendFormat(const value_type* fmt, ...)
		{
			va_list va;
			va_start(va, fmt);
			k_bstr_append_format_va(CastPtr(), SIZE, fmt, va);
			va_end(va);
		}

		void AppendFormatVa(const value_type* fmt, va_list va)
		{
			k_bstr_append_format_va(CastPtr(), SIZE, fmt, va);
		}

		void Lower()
		{
			k_bstr_lower(CastPtr());
		}

		void Upper()
		{
			k_bstr_upper(CastPtr());
		}

		void Trim()
		{
			k_bstr_trim(CastPtr());
		}

		void TrimLeft()
		{
			k_bstr_trim_left(CastPtr());
		}

		void TrimRight()
		{
			k_bstr_trim_right(CastPtr());
		}

		void Fill(value_type ch, kint count)
		{
			k_bstr_set_rep(CastPtr(), ch, count);
		}

		void AppendFill(value_type ch, kint count)
		{
			k_bstr_append_rep(CastPtr(), ch, count);
		}

		kint HasChars(const value_type* chars) const
		{
			return k_bstr_has_char(CastPtr(), chars);
		}

		kint Find(int pos, value_type ch) const
		{
			return k_bstr_find_char(CastPtr(), pos, ch);
		}

		kint Find(value_type ch) const
		{
			return k_bstr_find_char(CastPtr(), 0, ch);
		}

		bool Contains(value_type ch) const
		{
			return Find(ch) >= 0;
		}

		kint CompareTo(const BlueStr& str, bool igcase = false) const
		{
			return k_bstr_compare_bls(CastPtr(), str.CastPtr(), igcase);
		}

		kint CompareTo(const value_type* str, bool igcase = false) const
		{
			return k_bstr_compare(CastPtr(), str, igcase);
		}

		kint CompareTo(const BlueStr& str, ksize_t len, bool igcase = false) const
		{
			return k_bstr_compare_bls_length(CastPtr(), str.CastPtr(), (kint)len, igcase);
		}

		BlueStr SubString(kint pos, kint len = -1) const
		{
			this_type ret;
			k_bstr_sub_bls(ret.CastPtr(), CastPtr(), pos, len);
			return ret;
		}

		void RemoveChars(const value_type* list)
		{
			k_bstr_rem_chars(CastPtr(), list);
		}

		// RemoveAt

		// Insert

		Iterator Begin() const
		{
			return Iterator(&_data[0]);
		}

		Iterator End() const
		{
			return Iterator(&_data[_len]);
		}

		Iterator First() const
		{
			return Iterator(&_data[0]);
		}

		Iterator Last() const
		{
			return Iterator(&_data[_len - 1]);
		}

		Iterator begin() const
		{
			return Iterator(&_data[0]);
		}

		Iterator end() const
		{
			return Iterator(&_data[_len]);
		}

		Iterator first() const
		{
			return Iterator(&_data[0]);
		}

		Iterator last() const
		{
			return Iterator(&_data[_len - 1]);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator cend() const
		{
			return ConstIterator(&_data[_len]);
		}

		ConstIterator cfirst() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator clast() const
		{
			return ConstIterator(&_data[_len - 1]);
		}

		cast_type* CastPtr()
		{
			return (cast_type*)this;
		}

		const cast_type* CastPtr() const
		{
			return (cast_type*)this;
		}
	};

	template <ksize_t SIZE>
	inline bool operator==(const BlueStr<SIZE>& left, const BlueStr<SIZE>& right)
	{
		return k_bstr_compare_bls(left.CastPtr(), right.CastPtr(), false) == 0;
	}

	template <ksize_t SIZE>
	inline bool operator!=(const BlueStr<SIZE>& left, const BlueStr<SIZE>& right)
	{
		return k_bstr_compare_bls(left.CastPtr(), right.CastPtr(), false) != 0;
	}

	template <ksize_t SIZE>
	inline bool operator==(const BlueStr<SIZE>& left, const char* right)
	{
		return k_bstr_compare(left.CastPtr(), right, false) == 0;
	}

	template <ksize_t SIZE>
	inline bool operator!=(const BlueStr<SIZE>& left, const char* right)
	{
		return k_bstr_compare(left.CastPtr(), right, false) != 0;
	}

	template <ksize_t SIZE>
	inline bool operator==(const char* left, const BlueStr<SIZE>& right)
	{
		return k_bstr_compare(right.CastPtr(), left, false) == 0;
	}

	template <ksize_t SIZE>
	inline bool operator!=(const char* left, const BlueStr<SIZE>& right)
	{
		return k_bstr_compare(right.CastPtr(), left, false) != 0;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const BlueStr<SIZE>& left, const BlueStr<SIZE>& right)
	{
		BlueStr<SIZE> p(left);
		p += right;
		return p;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const BlueStr<SIZE>& left, const char* right)
	{
		BlueStr<SIZE> p(left);
		p += right;
		return p;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const BlueStr<SIZE>& left, char right)
	{
		BlueStr<SIZE> p(left);
		p += right;
		return p;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const char* left, const BlueStr<SIZE>& right)
	{
		BlueStr<SIZE> p(left);
		p += right;
		return p;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(char left, const BlueStr<SIZE>& right)
	{
		BlueStr<SIZE> p(left);
		p += right;
		return p;
	}
}

//////////////////////////////////////////////////////////////////////////
// stl containers
#include <string>
#include <array>

namespace tpl
{
	// string
#if defined(_XSTRING_) || defined(_BASIC_STRING_H)
	typedef std::basic_string<char, std::char_traits<char>, MemStlAlloc<char> > string;
	typedef std::basic_string<kwchar, std::char_traits<kwchar>, MemStlAlloc<kwchar> > wstring;
#endif

	// vector
#if defined(_VECTOR_) || defined(_STL_VECTOR_H)
	template <typename T, typename A = MemStlAlloc<T> >
	class vector : public std::vector<T, A>, public MemAlloc<>
	{
	public:
		typedef tpl::vector<T, A> this_type;
		typedef std::vector<T, A> super_type;
		typedef typename super_type::size_type size_type;

	public:
		vector(void)
			: super_type()
		{
		}

		explicit vector(size_type count)
			: super_type(count)
		{
		}

		vector(size_type count, const T &value)
			: super_type(count, value)
		{
		}

		vector(const this_type &right)
			: super_type(right)
		{
		}

		template<typename ITER>
		vector(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

#if _SB_CPP11_MOVE_
		vector(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// list
#if defined(_LIST_) || defined(_STL_LIST_H)
	template <typename T, typename A = MemStlAlloc<T> >
	class list : public std::list<T, A>, public MemAlloc<>
	{
	public:
		typedef tpl::list<T, A> this_type;
		typedef std::list<T, A> super_type;
		typedef typename super_type::size_type size_type;

	public:
		list(void)
			: super_type()
		{
		}

		explicit list(size_type count)
			: super_type(count)
		{
		}

		list(size_type count, const T &value)
			: super_type(count, value)
		{
		}

		list(const this_type &right)
			: super_type(right)
		{
		}

		template<typename ITER>
		list(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

#if _SB_CPP11_MOVE_
		list(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// deque
#if defined(_DEQUE_) || defined(_STL_DEQUE_H)
	template <typename T, typename A = MemStlAlloc<T> >
	class deque : public std::deque<T, A>, public MemAlloc<>
	{
	public:
		typedef tpl::deque<T, A> this_type;
		typedef std::deque<T, A> super_type;
		typedef typename super_type::size_type size_type;

	public:
		deque(void)
			: super_type()
		{
		}

		explicit deque(size_type count)
			: super_type(count)
		{
		}

		deque(size_type count, const T &value)
			: super_type(count, value)
		{
		}

		deque(const this_type &rhs)
			: super_type(rhs)
		{
		}

		template<typename ITER>
		deque(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

#if _SB_CPP11_MOVE_
		deque(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// queue
#if defined(_QUEUE_) || defined(_STL_QUEUE_H)
	template<typename T, typename C = deque<T> >
	class queue : public std::queue<T, C>, public MemAlloc<>
	{
	public:
		typedef tpl::queue<T, ContainerT> this_type;
		typedef std::queue<T, ContainerT> super_type;
		typedef typename super_type::size_type size_type;

	public:
		queue(void)
			: super_type()
		{
		}

		queue(const this_type& right)
			: super_type(right)
		{
		}

		explicit queue(const ContainerT &container)
			: super_type(container)
		{
		}

#if _SB_CPP11_MOVE_
		queue(this_type&& right)
			: super_type(right)
		{
		}

		queue(C&& cont)
			: super_type(cont)
		{
		}
#endif
	};
#endif

	// set
#if defined(_SET_) || defined(_STL_SET_H)
	template<typename T, typename P = std::less<T>, typename A = Allocator<T> >
	class set : public std::set<T, P, A>, public MemAlloc<>
	{
	public:
		typedef tpl::set<T, P, A> this_type;
		typedef std::set<T, P, A> super_type;

	public:
		set(void)
			: super_type()
		{
		}

		explicit set(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		set(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		set(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		set(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		set(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// map
#if defined(_MAP_) || defined(_STL_MAP_H)
	template<typename K, typename V,
		typename P = std::less<K>,
		typename A = MemStlAlloc<std::pair<K, V> > >
	class map : public std::map<K, V, P, A>, public MemAlloc<>
	{
	public:
		typedef tpl::map<K, V, P, A> this_type;
		typedef std::map<K, V, P, A> super_type;

	public:
		map(void)
			: super_type()
		{
		}

		explicit map(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		map(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		map(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		map(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		map(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// multi set
#if defined(_SET_) || defined(_STL_MULTISET_H)
	template<typename K,
		typename P = std::less<K>,
		typename A = MemStlAlloc<K> >
	class multiset : public std::multiset<K, P, A>, public MemAlloc<>
	{
	public:
		typedef tpl::multiset<K, P, A> this_type;
		typedef std::multiset<K, P, A> super_type;

	public:
		multiset(void)
			: super_type()
		{
		}

		explicit multiset(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		multiset(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		multiset(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		multiset(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		multiset(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// multi map
#if defined(_MAP_) || defined(_STL_MULTIMAP_H)
	template<typename K, typename V,
		typename P = std::less<K>,
		typename A = MemStlAlloc<std::pair<K, V> > >
	class multimap : public std::multimap<K, V, P, A>, public MemAlloc<>
	{
	public:
		typedef tpl::multimap<K, V, P, A> this_type;
		typedef std::multimap<K, V, P, A> super_type;

	public:
		multimap(void)
			: super_type()
		{
		}

		explicit multimap(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		multimap(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		multimap(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		multimap(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		multimap(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// unordered map
#if defined(_UNORDERED_MAP_) || defined(_UNORDERED_MAP_H)
	template<typename K, typename V,
		typename H = std::hash<K>, typename P = std::equal_to<K>,
		typename A = MemStlAlloc<K> >
	class unordered_map : public std::unordered_map<K, V, H, P, A>, public MemAlloc<>
	{
	public:
		typedef tpl::unordered_map<K, V, H, P, A> this_type;
		typedef std::unordered_map<K, V, H, P, A> super_type;
		typedef typename super_type::size_type size_type;
		typedef typename super_type::hasher hasher;

	public:
		unordered_map()
			: super_type()
		{
		}

		unordered_map(const this_type& right)
			: super_type(right)
		{
		}

		explicit unordered_map(size_type buckets)
			: super_type(buckets)
		{
		}

		unordered_map(size_type buckets, const hasher& hasharg)
			: super_type(buckets, hasharg)
		{
		}

#if 0
		unordered_map(size_type buckets, const hasher& hasharg, const _Keyeq& keyeqarg)
			: super_type(buckets, hasharg, keyeqarg)
		{
		}
#endif

		template<class ITER>
		unordered_map(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<class ITER>
		unordered_map(ITER frst, ITER last, size_type buckets)
			: super_type(frst, last, buckets)
		{
		}

		template<class ITER>
		unordered_map(ITER frst, ITER last, size_type buckets, const hasher& hasharg)
			: super_type(frst, last, buckets, hasharg)
		{
		}

#if 0
		template<class ITER>
		unordered_map(ITER frst, ITER last, size_type buckets, const hasher& hasharg, const _Keyeq& keyeqarg)
			: super_type(frst, last, buckets, hasharg, keyeqarg)
		{
		}
#endif

#if _SB_CPP11_MOVE_
		unordered_map(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif
}

// std extends
namespace std
{
#if defined(_BASIC_STRING_H)
	// string hasher for GCC, because GCC doesn't support type degrade.
	template<>
	struct hash<tpl::string> : public __hash_base<size_t, tpl::string>
	{
		size_t operator()(const tpl::string& s) const noexcept
		{ return std::_Hash_impl::hash(s.data(), s.length()); }
	};

	template <>
	struct __is_fast_hash<hash<tpl::string>> : std::false_type {};

	// wstring hasher for GCC, because GCC doesn't support type degrade.
	template<>
	struct hash<tpl::wstring> : public __hash_base<size_t, tpl::wstring>
	{
		size_t operator()(const tpl::wstring& s) const noexcept
		{ return std::_Hash_impl::hash(s.data(), s.length() * sizeof(wchar_t)); }
	};

	template <>
	struct __is_fast_hash<hash<tpl::wstring>> : std::false_type {};
#endif	
}
#endif	// __cplusplus

#if __GNUC__
#pragma GCC diagnostic pop
#endif

#if _MSC_VER
#pragma warning(pop)
#endif

#endif	// __SBCTN_H__
